
//3361.两个字符串的切换距离
class Solution {
    typedef long long LL;
public:
    long long shiftDistance(string s, string t, vector<int>& nextCost, vector<int>& previousCost) {
        //在进行转变的时候我们需要知道从一个字符到另一个字符需要的代价是多少
        //题目中已知的是每个字符转换的代价,所以可以使用前缀和得到从一个字符到另一个字符的代价
        vector<LL> lsum(27);   //i位置表示从a到i+'a'的代价
        vector<LL> rsum(27);   //i位置表示从z到'a'+i-1的代价

        for(int i = 0 ;i < 26 ;i++)
        {
            lsum[i+1] = lsum[i] + nextCost[i];
            rsum[25-i] = rsum[26-i] + previousCost[25-i];
        }
        //开始进行转换
        LL ret = 0;
        for(int i = 0 ;i <s.size(); i++)
        {
            if(s[i] == t[i]) continue;
            LL next, prev ;
            if(s[i] < t[i])                 //t[i]在后面
            {
                next = lsum[t[i]-'a'] - lsum[s[i]-'a'];
                prev = rsum[0] - rsum[s[i]-'a'+1] + rsum[t[i]-'a'+1];
            }
            else                            //t[i]在前面
            {
                next = lsum[26] - lsum[s[i]-'a'] + lsum[t[i]-'a'];
                prev = rsum[t[i]-'a'+1] - rsum[s[i]-'a'+1];
            }
            ret += min(next,prev);
        }
        return ret;
    }
};
